The present invention generally relates to computer graphics display systems, and more particularly, to techniques for applying texture to objects that are shown in the display. Even more specifically, this invention relates to a procedure for producing anisotropic texture using constant density object space stochastic sampling.
Many modern computer systems are able to display complex three-dimensional objects on display devices that are controlled by the computer systems, and commonly these complex objects are displayed interactively to allow the computer user to manipulate the objects. Well known graphics techniques for rendering these three dimensional objects such as Gouraud shading, hidden surface algorithms, clipping, filling polygons and coordinate transformations are used to generate the displayed object on a suitable device, such as a CRT video display that is controlled by the computer system.
Typically, in the operation of these computer systems, a polygon representation of the object is converted to a raster scanned image that is stored in a frame buffer. Usually, various parameter values, such as color, depth and translucency, are given for the vertices of the polygon, and in a process referred to as scan conversion, the computer uses the given values to compute values for these parameters for the pixels inside the polygon. The computed values are stored in the frame buffer at the resolution of the display device; and from that frame buffer, these values may be used to produce an image of the object on the display device.
Texture mapping is a commonly employed technique for adding detail in computer graphics rendering to achieve a high degree of realism in the rendered image. With this technique, image data needed to show the surface text for various objects, such as a road, the sky, a wheat field, or a brick wall, are stored in data arrays, referred to as texture maps, in the computer memory. When one of these objects is shown on the video display, data is obtained from the corresponding texture map and used to show the object on the display device with the desired surface texture.
In a common, simple texturing procedure, texture coordinates are specified for the vertices of each drawing polygon. These texture coordinates identify locations in the relevant texture map. As the polygon is rasterized pixel-by-pixel, these specified texture coordinates are used to determine, usually via an interpolation process, texture coordinates for each pixel. Then, as the image datum value for each pixel is being determined, the contents of the texture map are fetched, by means of the computed texture coordinates for that pixel, and used in the determination of that image datum.
Conventional texture mapping approaches used in real time and interactive graphic systems cannot achieve a quality texture mapping for shallow viewing angles of textured objects. This difficulty is demonstrated by a well-known example, referred to as the white line down the center of the road problem. In this example, the display system shows a white line down the center of a road. The white line is actually a series of white line segments, each segment is about ten feet long and five inches wide, and the line segments are separated by ten feet of black pavement. In showing this white line, the display system attempts to achieve two conflicting goals. The first goal is to keep the white line from disappearing as the viewer looks down the road, and the second goal is to prevent the white line from scintillating. Scintillation is manifested by the white line appearing for several segments (e.g., 50 feet), and disappearing for several segments (e.g., 50 feet).
Related problems are encountered when the display system attempts to show a building corner at a shallow angle. This building feature can be shown sharply when it directly faces the viewer, but the feature either scintillates or appears fuzzy when viewed at a shallow angle. As explained in greater detail below, these problems with conventional texturing systems are caused by the fact that the system does not account for the pixel""s elongated footprint when the pixel is projected, or mapped, onto the texture map.
Texture maps are described in detail in U.S. Pat. No. 4,727,365, the disclosure of which is incorporated herein by reference. Generally, texture maps are organized into sets or series, with each set having a number of individual texture maps, referred to as Levels of Detail or LODs. Typically, each set has a base or highest resolution map, and successive maps in the set are reduced resolution versions of that base map. This base map is often referred to as LOD(0), and the successively lower resolution maps in the set are referred to as LOD(1), LOD(2), LOD(3), and so on. Commonly, each of these successive maps is a 2- to -1 reduction in each of the two dimensions of the previous map in the set. Thus, for example, if the base, or highest resolution, texture map in a set is 512 by 512 texels, then LOD(1) is a texture map that is 256 by 256 texels (individual elements of a texture map). Subsequent texture maps can continue to be formed until LOD(9) is produced, which would be a map that is 1 texel by 1 texel.
In the texturing process, the pixel is, in effect, projected onto a texture map, a process referred to as mapping the pixel into texture space. Then, two LOD values are determined based, respectively, on the width and the length of the projection of the pixel onto the texture map. The larger of these two values is taken as the effective, or actual, LOD value for the pixel.
After an LOD value is determined for a pixel, a texture value may be calculated for the pixel using any of a number of specific procedures. For instance, after the LOD value is calculated, the two texture maps with integer LODs that bracket the pixel""s effective LOD value may be determined. Interpolation between adjacent texels in one or both of these LODs may be performed to calculate the value of the mapped pixel. Examples of current methods used to calculate pixel intensity include procedures referred to as nearest texel neighbor, bi-linear interpolation using texels in one of the integer LODs, and tri-linear interpolation uses bi-linear interpolation on two adjacent LODs and linearly blends the results from each of the bi-linear interpolations.
These forms of texture mapping are said to be isotropic, since the LOD value for the projected pixel is assumed to be equal along both the length and the width of the projection of the pixel onto the texture map. This isotropic assumption produces excellent results for pixels that project substantially orthogonally onto a textured surface. However, this assumption may produced some errors for pixels with elongated projections onto the texture map, for instance as shown in FIG. 1.
Anisotropic texture approaches that account for a projected pixel""s elongated shape in texture space have been implemented, but only for non real time systems. Such approaches fall into two broad categories: 1) methods for convoluting the pixel""s projection in texture space with the texture values, and 2) methods using the storage of pre-processed and pre-filtered textured maps. The former methods can be very accurate but computationally very expensive. The latter methods require less computations than the former, but are less flexible, less precise, and are memory intensive.
Because of an increasing demand for more and more different textures maps to be available in a graphics display system for real time and interactive applications, the texturing approaches that are less memory intensive are more desirable.
U.S. Pat. No. 5,651,104 for xe2x80x9cComputer Graphics System And Process For Adaptive Supersamplingxe2x80x9d addresses the problem of anisotropic texture mapping. FIG. 1 shows the projection of a pixel onto a texture map. This patent suggests sampling regularly along the substantially longitudinal axis of the pixel""s projection onto the texture map. Several difficulties arise, though, when sampling in the prescribed manner. A first difficulty is that the samples will miss texture variations that are off that longitudinal axis. To elaborate, with this procedure, when the pixel is projected into texel space, regular samples are taken from the texture map along the substantially longitudinal axis of the pixel projection. Some texels will not be sampled, and other texels will be sampled multiple times.
Another difficulty with this prior art approach is that scintillation will normally occur when the sampling axis is parallel to the texture grid. In this situation, as motion is introduced to an image, there are times when all of the sample points switch texels at the same time. As an example, when the image is that of a roadway with a line extending along the roadway center, if the viewpoint is shifted slightly to the right and then back to the left, the line may suddenly disappear from and then reappear in the image.
Another problematic situation occurs when the projection of the pixel onto the texture map, referred to as the pixel footprint, has a diamond shape. A first specific difficulty with this situation is deciding which of the footprint axes to choose, since both axes are of equal length. A second difficulty is a lack of correct sampling, as demonstrated in FIG. 2.
Several previous patents, including U.S. Pat. Nos. 4,897,806, 5,025,400, and 5,239,624, have addressed the pseudo-random point sampling of pixels, but these references are directed to the anti-aliasing aspect of polygon edges. Neither the texture anti-aliasing nor the isotropic vs. anisotropic texture filtering concepts are discussed in these patents.
These patents suggest the use of stochastic samples throughout the pixel. In particular, these references describe techniques in which these sample points are constrained such that a Fourier transform over a distribution of the sample points over an infinite extent contains substantially continuous regions. The requirement of a substantially continuous Fourier transform distribution over an infinite extent of samples in pixel space (screen space) does not guarantee or generate appropriate anisotropic texture mapping in object space.
A continuous Fourier distribution constraint on sub-pixel sample point locations in screen space does not provide for a variation of samples per pixel as a function of the number of texels covered by the projection of the pixel in texture space. When the pixels project into texture space, they are usually elongated, and this method will under-sample the pixel. If the number of samples in each pixel is increased to compensate for this under-sampling, then other pixels will be oversampled. Specifically, with reference to FIG. 3, those pixels whose projection covers only a few texels, or even less than a texel, will be oversampled. This oversampling wastes system resources, as well as time.
An improved anisotropic texturing procedure is disclosed in copending U.S. patent application Ser. No. 08/975,133, for xe2x80x9cAnisotropic Texture Mapping Using Silhouette Footprint Analysis Image Generation System,xe2x80x9d the disclosure of which is herein incorporated by reference. This texturing technique uses a constant sample density, regularly spaced in each texel. Aliasing occurs when this method is used, however, when the texel grid and the pixel footprint are parallel. With this procedure, as particularly illustrated in FIG. 4, as the viewpoint shifts slightly from one frame to the next frame, a whole set of sample points that are included in the first frame are excluded from the next frame. This results in scintillation caused by an abrupt color shift, as opposed to a more gradual shift in color over several frames.
An object of this invention is to provide a computationally efficient, high fidelity texture mapping procedure.
Another object of the present invention is to provide an anisotropic texture mapping procedure using stochastic sampling with constant density in object space.
A further object of this invention is to use stochastic sampling to prevent scintillation when an anisotropic texture mapping procedure is used in a computer graphics display system.
These and other objects are attained with a method and apparatus, in a computer graphics display system, for mapping texture anisotropically onto a group or set of pixels. The method and apparatus are for use with a computer graphics display system that has texture values that form a texture map including an array of texels. The method comprises the steps of, for each of the pixels, determining a footprint for the pixel on the array of texels, using a stochastic sampling procedure to identify locations for a multitude of sample points in that footprint, and maintaining the density of the sample points approximately constant throughout the footprint. The method further comprises the steps of assigning a value to each of the sample points based on the location of the sample point on the array of texels, and determining a pixel intensity value using the values assigned to the sample points.
With a preferred embodiment of the invention, like the silhouette method, a pixel is mapped into an LOD texture map based on the number of texels a given footprint projection encompasses. A texel neighborhood is selected, based on texture memory bandwidth limitations; and this neighborhood can be selected in square spans, in rectangular spans, or selectively, based on the number of texels needed and the memory fetch capabilities.
Samples are then taken, stochastically, with a set density in texel space. The locations of the stochastic samples can be generated during run time, or can be fetched from a look-up table containing a previously generated pattern. The sample points are arranged within the pixel footprint, and an average pixel intensity is computed from values obtained from all of the samples.
The present invention provides a computationally efficient process of averaging all the texels and fractional texels that fall inside the pixel footprint and determines a single value for the mapped pixel. This texture mapping procedure retains the high fidelity of the more precise method of convolving the pixel""s projected area with all of the covered and fractional texels of the highest resolution texture map but without the associated computational complexity.
Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description, given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.